定理1:
令$G$为一个阶数$n\geq 3$的图,如果对于任意整数$j$,满足$1\leq j < \frac{n}{2}$,$G$图中度数至多为$j$的节点个数少于$j$,那么图$G$是哈密顿图。
理解:
比较直观的理解一下就是,对于一个图,我们可以枚举$j$从$1$到$\frac{n}{2}$,比如度数至多为1的节点少于1个,度数至多为2的节点少于2个……
很容易发现,这是一个非常紧的定理,而且如果能够拿到所有节点的度的序列的话,完全可以在$O(n)$的时间复杂度下快速判断出一个图是否为哈密顿图。
前置定理:
定理:假设$u,v$是图$G$上的两个不相邻的点,但是满足$d(u)+d(v) \geq n$。那么图$G+uv$是哈密顿图当且仅当图$G$是哈密顿图。
证明:充分性是显然的。下面证明必要性:如果一个图$G+uv$是一个哈密顿图并且节点$u,v$是图上不相邻的两个点,然后图$G$不是一个哈密顿图。这意味着在图$G+uv$中的每一个哈密顿圈都需要经过$u-v$之间的路。所以$d(u) + d(v) \geq n$,$G$必然为哈密顿图,矛盾。
这意味着,我们在研究哈密顿性质是否存在的时候,可以先将图扩展到一个边数尽可能多的情况,因为他们是相互等价的。
一个图闭包(closure)的生成:
图$G$的闭包$C(G)$是:在图$G$中满足$d(u) + d(v) \geq n$且不相邻的一对节点$u,v$之间加入一条边,递归地重复上述过程,直到不存在满足要求的点对。
有关闭包的一些结论
定理:一个图的闭包是良定义的(按照不同的顺序递归生成结果一致)
定理:一个图是哈密顿图当且仅当它的闭包也是哈密顿图。
推论:一个阶数至少为3的图$G$,如果它的闭包$C(G)$是完全图,那么$G$是哈密顿图。
证明:
假设,该定理不成立。对于$C(G)$中的所有不相邻的节点,让$u,w$是一对度数和最大的节点。
显然$d_{C(G)}(u)+d_{C(G)}(v) \leq n-1$,我们不妨令u为度数较小的那个点。
令$d_{C(G)}(u) = j$,那么$j\leq \frac{n-1}{2}$,并且有$$d_{C(G)}(w) \leq n-j-1$$令$W$为所有不与$w$所相邻的点的集合,因此$u \in W$。观察到如果$v\in W$,那么就会有$d_{C(G)}(v)\leq j$,否则的话$$d_{C(G)}(v)+d_{C(G)}(w) > d_{C(G)}(u) + d_{C(G)}(w)$$这会导致与点$u$的定义相矛盾。
因此,集合$W$中每个节点的度数均至多为$j$。因为在假设中,$|W|\leq j-1$,因此
$$d_{C(G)}(w) \geq (n-1)-(j-1) = n-j$$ 矛盾!